//https://www.luogu.com.cn/problem/P4017
//题意：给一个图，求出从起点到终点一共有多少种路线（不存在环）
//思路：拓扑排序，找到入度为0，和出度为0的点，入度为0为起点，权值加一入队，
//队头出队，将队头点所连接的点，权值加上队头权值入度减一，将入度为0的点依次入队，重复操作，直到队列为空，最后将出度为0的点权值加入答案中
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005;
const int MAXM=500005;
const int MOD=80112002;
int head[MAXN]={0},in[MAXN]={0},out[MAXN]={0},to[MAXM]={0},nex[MAXM]={0},num[MAXN]={0},cot=0,ans=0;
queue<int> q;
void add(int u,int v){
    to[++cot]=v;
    nex[cot]=head[u];
    head[u]=cot;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        out[x]++;
        in[y]++;//统计出度入度
    }
    for(int i=1;i<=n;i++){
        if(in[i]==0){
            q.push(i);
            num[i]++;//入度为0权值+1，入队
        }
    }
    while(!q.empty()){
        int np=q.front();
        q.pop();//拿出队头
        for(int i=head[np];i;i=nex[i]){
            num[to[i]]+=num[np];
            num[to[i]]%=MOD;//将队头权值累加进后的点
            in[to[i]]--;//出度减少
            if(in[to[i]]==0) q.push(to[i]);
        }
    }
    for(int i=1;i<=n;i++){
        if(out[i]==0){
            ans+=num[i];
            ans%=MOD;//累加答案
        }
    }
    printf("%d",ans);
    return 0;
}
